package top;

import java.util.Arrays;

/**
 *
 * 摆动序列II
 * 先排序，再将前后两半部分依次倒叙插入
 *
 * @author chenyw
 * @date 2022/7/21 10:09
 */
public class Top324wiggleSort {
    public void wiggleSort(int[] nums) {
        //复制数组
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int x = (nums.length + 1) / 2;
        //j负责前半部分的倒序插入， k负责后半部分的倒序插入
        for (int i = 0, j = x - 1, k = nums.length - 1; i < nums.length; i += 2, k--, j--) {
            //前半部分倒序插入
            nums[i] = arr[j];
            //后半部分
            if (i + 1 < nums.length) {
                nums[i + 1] = arr[k];
            }
        }
    }
}
